#include "main/utils.h"
using namespace std;

bool indexAndValueInRange(const vector<int>& vec, const int& k, const int& t) {
  set<int> help_set;
  for (int i = 0; i < vec.size(); ++i) {
    auto iter = help_set.lower_bound(vec[i] - t);
    if (iter != help_set.end() && *iter <= vec[i] + t) {
      return true;
    }
    help_set.insert(vec[i]);
    if (i >= k) {
      help_set.erase(vec[i - k]);
    }
  }
  return false;
}

int getId(const int& num, const int& size) {
  return num < 0 ? (num + 1) / size - 1 : num / size;
}

bool indexAndValueInRange1(const vector<int>& vec, const int& k, const int& t) {
  map<int, int> help_map;
  for (int i = 0; i < vec.size(); ++i) {
    int id = getId(vec[i], t + 1);
    if (help_map.count(id) ||
        (help_map.count(id - 1) && abs(help_map[id - 1] - vec[i]) <= t) ||
        (help_map.count(id + 1) && abs(help_map[id + 1] - vec[i]) <= t)) {
      return true;
    }
    help_map[id] = vec[i];
    if (i >= k) {
      help_map.erase(getId(vec[i - k], t + 1));
    }
  }
  return false;
}

int main() {
  vector<int> vec = {1, 2, 3, 1};
  int k = 3, t = 0;
  bool ret = indexAndValueInRange(vec, k, t);
  cout << ret << endl;

  bool ret1 = indexAndValueInRange1(vec, k, t);
  cout << ret1 << endl;
  cout << endl;

  return 0;
}
